package 中等.搜索.深度优先搜索;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值
 * 代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或
 * 对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。
 * 编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/pond-sizes-lcci
 */
public class 水域大小_16_19 {

    public static void main(String[] args) {

    }

    /**
     * 深度优先搜索
     * 找到为 0 的水域，找出其相邻的水域，统计池塘的大小
     * ，并标记为 1 ，避免重复统计
     */
    public int[] pondSizes(int[][] land) {
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < land.length; i++) {
            for (int j = 0; j < land[0].length; j++) {
                if (land[i][j] == 0) {
                    // 公共变量，需要初始化值
                    sum = 0;
                    dfs(i, j, land);
                    list.add(sum);
                }
            }
        }

        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        Arrays.sort(arr);
        return arr;
    }

    private int sum;

    int[][] direction = {{-1, 0}, {-1, -1}, {-1, 1}, {0, -1}, {0, 1}, {1, 0}, {1, 1}, {1, -1}};

    private void dfs(int i, int j, int[][] land) {
        land[i][j] = 1;
        sum++;

        for (int[] direct : direction) {
            int nextI = i + direct[0];
            int nextJ = j + direct[1];

            if (nextI >= 0 && nextI < land.length &&
                    nextJ >= 0 && nextJ < land[0].length &&
                    land[nextI][nextJ] == 0) {

                dfs(nextI, nextJ, land);
            }
        }
    }

}
